#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2003,M=1e6+4;
int n,a[N],b[M],l[N];
LL f[N][N][2],g[N][2];
int Main()
{
	LL ans=0;
	memset(b,0,sizeof b);
	memset(f,0,sizeof f);
	scanf("%d",&n);
	for(int i=1;i<=M-4;i++) b[i]=-1000;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(b[a[i]]) l[i]=b[a[i]];
		b[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			
			if(l[i]==i-1) f[i][j][0]=f[i-1][j][0]+a[i];
			else f[i][j][0]=f[i-1][j][0];
			if(l[i]==i-1) f[i][j][1]=f[i-1][j][1]+a[i];
			else f[i][j][1]=f[i-1][j][1];
			if(j-1==l[i]) f[i][j][0]=max(f[i][j][0],f[i-1][j][1]+a[i]);
			else f[i][j][0]=max(f[i][j][0],f[i-1][j][1]);
			if(j-1==l[i]) f[i][j][1]=max(f[i][j][1],f[i-1][j][0]+a[i]);
			else f[i][j][1]=max(f[i][j][1],f[i-1][j][0]);
			f[i][j][0]=max(f[i][j][0],g[i-1][1]);
			f[i][j][1]=max(f[i][j][1],g[i-1][0]);
			g[i][0]=max(g[i][0],f[i][j][0]);
			g[i][1]=max(g[i][1],f[i][j][1]);
		}
	} 
	for(int i=0;i<=n;i++) ans=max(ans,f[n][i][0]);
	printf("%lld\n",ans);
	return 0;
}
int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
    int Case=1;
    scanf("%d",&Case);
    while(Case--) Main();
	return 0;
}
